package com.gitee.feizns.explore.data_structure.linked_list.singly.isPalindrome;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/4
 */
public class IsPalindrome {

    public static void main(String[] args) {
        System.out.println(isPalindrome(create()));
    }

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
        ret.next.next = new ListNode(2);
        ret.next.next.next = new ListNode(1);
        return ret;
    }

    static ListNode tmp = null;

    public static boolean isPalindrome(ListNode head) {
        if ( head == null || head.next == null )
            return true;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode fast = prev;
        ListNode slow = prev;
        while ( fast.next != null && fast.next.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }

        if ( fast.next != null )
            slow = slow.next.next;
        else
            slow = slow.next;

        tmp = head;

        return equals(slow);
    }


    private static boolean equals(ListNode tmp1) {
        if ( tmp1 != null ) {
            if ( equals(tmp1.next) ) {
                ListNode t = tmp;
                tmp = tmp.next;
                if ( tmp1.val == t.val )
                    return true;
            }
            return false;
        }
        return true;
    }

}
